/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package jobscheduling.algorithms.glowworm;

import java.awt.print.Paper;
import java.util.Arrays;
import java.util.Map;
import java.util.Random;
import java.util.TreeMap;

import jobscheduling.algorithms.AbstractScheduler;
import jobscheduling.algorithms.ResultListener;
import jobscheduling.model.InputData;
import jobscheduling.model.SolutionEvaluator;

/**
 *
 * @author Dawid, Łukasz Jeleń
 */
public class GlowwormScheduler extends AbstractScheduler{
    private static final Map<String, String> _params = new TreeMap<String, String>();
    private static final Map<String, String> _descs = new TreeMap<String, String>();
    
	private int machines; // ilosc
	private int tasks; // ilosc
	private int ilosc; /* swietlikow */
	private Firefly[] ffs; /* swietliki */
	private int best; /* indeks najlepszego swietlika */
    private int bestTime = Integer.MAX_VALUE; /* trzyma najlepszy czas dotychczas, pomocniczo */
	/* parametry */
	private int[] bestPermutation;  /* najlepsza do tej pory znaleziona permutacja */
    private double gamma; /* absorpcja */
	private double beta0;
	private double minimumBeta; /* nirzależnie od odległości takie beta będzie co najmniej */
	private double alpha; /* losowość */
	private double alphaLimitFactor; /* współczynnik zmiany losowości po każdej iteracji (alpha = alpha * alphaLimitFactor */
	private double exponent; /* wykładnik przy exp(-gamma*r^x) */
    
    static {
        _params.put("gamma", "1.0");
        _params.put("alpha", "2.0");
        _params.put("alphaLimitFactor", "1.0");
        _params.put("beta0", "10.0");
        _params.put("minimumBeta", "0.1");
        _params.put("exponent", "2");
        _params.put("number", "30");
        _params.put("iterations", "1000");

        _descs.put("gamma", "Light absorption coefficient");
        _descs.put("alpha", "Randomness");
        _descs.put("alphaLimitFactor", "Randomness limitation coefficient");
        _descs.put("beta0", "Base attractiveness");
        _descs.put("minimumBeta", "Minimum attractiveness");
        _descs.put("exponent", "Value of exponent for computing attractiveness");
        _descs.put("number", "Number of fireflies");
        _descs.put("iterations", "Numeber of iterations");
    }
    
    public GlowwormScheduler (int[][] jobList, ResultListener listener, 
                              Map<String, String> params){
        super(jobList, listener, params);
        /* ilosci */
        machines = jobList.length;
		tasks = jobList[0].length;
		/* odczyt parametrów */
		ilosc = Integer.parseInt(params.get("number"));
		gamma = Double.parseDouble(params.get("gamma"));
		beta0 = Double.parseDouble(params.get("beta0"));
		minimumBeta = Double.parseDouble(params.get("minimumBeta"));
		alpha = Double.parseDouble(params.get("alpha"));
		alphaLimitFactor = Double.parseDouble(params.get("alphaLimitFactor"));
		exponent = Double.parseDouble(params.get("exponent"));
		/* init swietlikow */
		ffs = new Firefly[ilosc];
		for (int i = 0; i < ilosc; i++)
			ffs[i] = new Firefly(); /* po konstrukcji maja
										juz wylosowana permutacje
										startowa */
		bestPermutation = new int[tasks];
		
		findBest(); /* znajdz najlepszego w poczatkowej konfiguracji */

    }
    
    public static Map<String, String> getParamsPresets() {
        return _params;
    }

    public static Map<String, String> getParamsDescs() {
        return _descs;
    }
    

	/* Klasa swietlika */
	public class Firefly implements Comparable
	{
		private int[] permutation; /* aktualna permutacja */
		private boolean[] occupied; /* pomocnicza przy losowaniu
		 							i uaktualnianiu permutacji */
		private Random r = new Random();
		private int time; /* makespan dla permutacji tego swietlika - 
		 				czyli to, co minimalizujemy */
		private double[][] position; /* pozycja tego swietlika */
		
		public Firefly() {
			/* init */
			permutation = new int[tasks];
			position = new double[tasks][tasks];
			int num;
			occupied = new boolean[tasks];
			
			/* wszystko na false - wskazuje, czy dane liczby 
			 * juz wykorzystane sa w permutacji
			 */
			for (int i = 0; i < tasks; i++)
				occupied[i] = false;
			/* losowanie permutacji poczatkowej */
			for (int i = 0; i < tasks; i++) {
				do { /* szukaj jeszcze nie uzytej liczby */
					num = r.nextInt(tasks);
				} while (occupied[num]);
				occupied[num] = true; /* zajmij ja */
				permutation[i] = num; /* dopisz do perm. */
			}
			
			/* wyznacz czas poczatkowej permutacji */
			updateMakespanTime();
		}
		
		public int[] getPermutation() {
			return permutation;
		}
		
		public int getTime() {
			return time;
		}
		
		/* aktualizacja makespanu */
		public void updateMakespanTime() {
			time = SolutionEvaluator.getEval(new InputData(machines, tasks, _jobs), permutation);
		}
		
		/* inicjalizuje wektor polozenia wedlug przyjetej dyskretyzacji */
		public void initPosition() {
			
			for (int i = 0; i < tasks; i++)
				for (int j = 0; j < tasks; j++)
					/* metoda:
					 * 1 gdy i-te zadanie jest j-te w kolejnosci
					 * 0 w przeciwnym wypadku
					 */
					position[i][j] = permutation[j] == i ? 1 : 0;
		}
		
		private void moveTowards(Firefly neighbour) {
			double distance = 0.0; /* odleglosc (potrzebne do czlonu beta_0 * exp(...) ) */
			/* policz euklidesowo odleglosc */
			for (int i = 0; i < tasks; i++)
				for (int j = 0; j < tasks; j++)
					distance += Math.abs(position[i][j] - neighbour.position[i][j]);
			/* metryka Euklidesowa */
			distance = Math.sqrt(distance);
			/* drugi czlon wzoru na nowe polozenie */
			double beta = (beta0 - minimumBeta) * Math.exp(-gamma * Math.pow(distance, exponent)) +
					minimumBeta;
			/* zaktualizuj polozenie aktualnego swietlika */
			for (int i = 0; i < tasks; i++)
				for (int j = 0; j < tasks; j++)
					position[i][j] = position[i][j] * (1.0 - beta) +
					(neighbour.permutation[j] == i ? 1.0 : 0.0) * beta + alpha * (r.nextDouble() - 0.5);
			
		}
			
		public void applyNewPermutation() {
			/* wyznacz prawdopodobienstwa
			 */
			for (int i = 0; i < tasks; i++)
				for (int j = 0; j < tasks; j++)
					position[i][j] = 1.0 / (1.0 + Math.exp(-position[i][j]));
			
			/* czas na wyznaczenie nowej permutacji
			 * Prawdopodobienstwo dotyczy "checi" objecia przez dane
			 * zadanie danego miejsca w permutacji, dlatego dajemy
			 * szanse najwiekszym prawdopodobienstwom. Kod
			 * wyjasnia o co chodzi dokladnie
			 */
			
			/* oznaczamy wszystkie pozycje w permutacji jako
			 * jeszcze nie uzyte
			 */
			for (int i = 0; i < tasks; i++)
				occupied[i] = false;
			/* pomocnicza anty-breakowa zmienna */
			boolean assigned;
			for (int i = 0; i < tasks; i++) {
				assigned = false; /* nic jeszcze sie nie stalo, wiec
									to jeszcze nie koniec */
				do { /* probuj znalezc najwyzszy mozliwy priorytet dla danego zadania */
					/* szukaj maksimum */
					int max = 0; /* to jest indeks, nie wartosc */
					for (int j = 1; j < tasks; j++)
						if (position[i][j] > position[i][max])
							max = j;
					if (occupied[max]) /* czy ktos juz zabral te pozycje permutacji */
						position[i][max] = -1.0; /* jesli tak, zmniejsz jej prawdopodobienstwo
										do poziomu ponizej niemozliwegp :) zeby nie mieszalo
						 				 i mozna bylo szukac kolejnych najwiekszych w kolejnej
						 				 iteracji */
					else { /* jupikaje! */
						permutation[max] = i; /* wloz do permutacji */
						occupied[max] = true; /* zablokuj innym */
						assigned = true; /* jedziemy do nastepnego zadania */
					}
				} while (!assigned);
			}
		}
		
		/* specjalny dodatek dla najlepszego, sprawdza
		 * poprzez zamiane sasiadujacych elementow czy moze
		 * nie udalo by sie dzieki temu poprawic sie jeszcze.
		 * W dokumentacji spokojnie można to nazwać poszukiwaniem
		 * lokalnym
		 */
		private void localSearch() {
			boolean swapped = false; /* znow anty-breakowa zmienna */
			for (int i = 0; i < tasks - 1 && !swapped; i++) {
				int temp; /* do zamiany */
				/* zamiana i-tego z (i+1)-wszym */
				temp = permutation[i];
				permutation[i] = permutation[i + 1];
				permutation[i + 1] = temp;
				/* czy jest lepiej? */
				int newTime = SolutionEvaluator.getEval(new InputData(machines, tasks, _jobs), permutation);
				if (newTime < time) {
					time = newTime;
					updateBestPermutation();
					swapped = true;
				}
				else { /* jesli nie ma poprawy, przywroc poprzednia */
					temp = permutation[i];
					permutation[i] = permutation[i + 1];
					permutation[i + 1] = temp;
				}
			}
		}

		/* Relacja: lepszy świetlik > gorszy świetlik, tj. wygrywa ten o mniejszym makespanie */
		@Override
		public int compareTo(Object o) {
			try {
				return ((Firefly)o).getTime() - this.getTime();
			}
			catch (ClassCastException e) {
				return 0;
			}
		}
	}
	
	/* kopiuje permutacje najlepszego jako najlepsza */
	public void updateBestPermutation() {
		for (int i = 0; i < ffs[best].permutation.length; i++)
			bestPermutation[i] = ffs[best].permutation[i];
	}
	
	/* wyznacza najlepszego swietlika */
	public void findBest() {
		int bestTime = Integer.MAX_VALUE;
		for (int i = 0; i < ffs.length; i++) /* liniowe poszukiwanie */
			if (ffs[i].time < bestTime) {
				bestTime = ffs[i].time;
				best = i;
			}
		if (ffs[best].time < this.bestTime) {
			this.bestTime = ffs[best].time;
			updateBestPermutation();
		}
	}
	

    @Override
    public boolean isCorrect(String parameter, String value) {
    	if ("number".equals(parameter) || "iterations".equals(parameter)) {
    		int val = 0;
    		 try {
 	        	val = Integer.parseInt(value);
 	        }
 	        catch (NumberFormatException e) {
 	        	return false;
 	        }
    		if (val < 0)
    			return false;
    	}
    	else {
	    	double val = 0.0;
	        try {
	        	val = Double.parseDouble(value);
	        }
	        catch (NumberFormatException e) {
	        	return false;
	        }
	        
	        if (val < 0.0)
	        	return false;
	        
	        if ("alphaLimitFactor".equals(parameter)) {
	        	if (val > 1.0)
	        		return false;
	        }
    	}
    	return true;
    }
    
    public void limitRandomness(int iterations) {
    	double delta = 1.0 - Math.pow((Math.pow(10.0, -4) / 0.9),
    			(1.0 / iterations));
    	alpha *= (1.0 - alphaLimitFactor * delta);
    	
    	//System.out.printf("%f\n", alpha);
    }
    
    @Override
    public void run(){
        int iterations = Integer.parseInt(_params.get("iterations"));
        for (int i = 0; i < iterations; ++i){
        	//System.out.println("Iter " + String.valueOf(i));
        	/* inicjuj pozycje */
        	for (int j = 0; j < ffs.length; j++) {
        		ffs[j].initPosition();
        	}
        	/* posortuj świetliki wedlug malejacych makespanow */
        	Arrays.sort(ffs);
        	
        	/*int[] temp = new int[ffs.length];
        	for (int j = 0; j < ffs.length; j++)
        		temp[j] = ffs[j].getTime();*/
        	
    		/* porownaj kazdego z kazdym */
    		for (int j = 0; j < ffs.length; j++)
    			for (int k = 0; k < ffs.length; k++) {
    				/* time jest tak na prawde funkcja celu, a -time intensywnoscia */
    				if (ffs[j].time > ffs[k].time) { /* jsli jest jasniejszy */
    					ffs[j].moveTowards(ffs[k]); /* rusz dupsko */
       				}
    			}
    		/* najlepszy (czyli ostatni w tablicy - była sortowana) rusza się losowo */
    		Firefly bestOne = ffs[ffs.length - 1];
    		for (int j = 0; j < tasks; j++)
    			for (int k = 0; k < tasks; k++)
    				bestOne.position[j][k] +=
    				(bestOne.r.nextDouble() - 0.5) * alpha;
    		
    		/* pozycje wyznaczone - czas wygenerować nową permutację
    		 * i zaktualizować funkcję celu
    		 */
    		for (int j = 0; j < ffs.length; j++) {
    			ffs[j].applyNewPermutation();
    			ffs[j].updateMakespanTime();
    		}
    		
    		/*for (int j = 0; j < ffs.length; j++)
    			if (ffs[j].time < temp[j])
    				System.out.printf("%d poprawił się z %d na %d\n", j, temp[j], ffs[j].getTime());
    		*/
    		
    		/* wyznacz nowego najlepszego w celu lokalnego poszukiwania */
    		findBest();
    		//System.out.printf("Najlepszy: %d (%d)\n\n", best, ffs[best].time);
    		/* i kaz mu sie sprobowac poprawic */
    		ffs[best].localSearch();
            this._result.newResult(bestPermutation.clone(), bestTime);
            /* zmniejsz losowość */
            limitRandomness(iterations);
        }
    }
}
